package test6;

import java.util.*;

class Solution2 {
    public static void main(String[] args) { //Dijkstra - 使用优先队列
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入结点个数：");
        int num = sc.nextInt();
        diGraphAdList graph = new diGraphAdList(num);
        for (int i = 0; i < num; i++) {
            System.out.println("请输入与第" + i + "个点相邻点的个数：");
            int node = sc.nextInt();
            System.out.println("请分别输入该点及其相邻点的名称和到该点的权值：");
            for (int j = 0; j <= node; j++) {
                String value = sc.next();
                int weight = sc.nextInt();
                graph.addNode(value, weight, i);
            }
        }
        graph.showGraphAdList();
        System.out.println("请输入开始结点：");
        String start = sc.next();
        graph.dijkstra(start);
    }
}

class pair implements Comparable {
    int dist;
    String value;
    pair(int dist, String value){
        this.dist = dist;
        this.value = value;
    }

    @Override
    public int compareTo(Object o) {
        if (o instanceof pair) {
            pair other = (pair) o;
            if (this.dist < other.dist) {
                return 1;
            } else if (this.dist > other.dist) {
                return -1;
            }
        }
        return 0;
    }
}

class diNode{
    String value;
    diNode next;
    int weight;
    public diNode(){}
}

class diAdList{
    diNode firstNode;
    public diAdList(){}

    public void add(String value, int weight){
        if (firstNode == null){
            firstNode = new diNode();
            firstNode.value = value;
            firstNode.weight = weight;
        }else {
            diNode p = firstNode;
            while (p.next != null){
                p = p.next;
            }
            p.next = new diNode();
            p.next.value = value;
            p.next.weight = weight;
        }
    }

    public void showList(){
        System.out.print(firstNode.value + "(" + firstNode.weight + ")");
        diNode p = firstNode;
        while(p.next != null){
            System.out.print("->" + p.next.value + "(" + p.next.weight + ")");
            p = p.next;
        }

    }
}

class diGraphAdList{
    int size;
    diAdList[] adLists;

    public int getPos(String value){
        for (int i = 0; i < size; i++) {
            if (adLists[i].firstNode.value.equalsIgnoreCase(value)){
                return i;
            }
        }
        return -1;
    }

    public void dijkstra(String value){
        int[] visited = new int[size];
        String[] parent = new String[size];
        String start = value;
        int[] distance = new int[size];
        for (int i = 0; i < size; i++) {
            distance[i] = 9999;
        }
        distance[getPos(value)] = 0;
        pair pair = new pair(0, value); //将点到起始点的距离和点的名称打包到pair类
        int dist, node;
        diNode p;
        PriorityQueue<pair> queue = new PriorityQueue<>();
        queue.add(pair);
        while (!queue.isEmpty()){
            pair = queue.poll();
            dist = pair.dist;
            value = pair.value;
            node = getPos(value);
            p = adLists[node].firstNode;
            while (p.next != null){
                if (visited[getPos(p.next.value)] == 0 && dist + p.next.weight < distance[getPos(p.next.value)]){
                    parent[getPos(p.next.value)] = value;
                    distance[getPos(p.next.value)] = dist + p.next.weight;
                    queue.add(new pair(dist + p.next.weight, p.next.value));
                }
                p = p.next;
            }
        }
        for (int i = 0; i < size; i++) {
            System.out.print(start + "到" + adLists[i].firstNode.value + "的最短距离为：" + distance[i] + '\t');
            if (distance[i] == 9999){
                System.out.println("不可达！");
                continue;
            }
            System.out.print("最短路径为：");
            int v = i;
            String path = adLists[i].firstNode.value;
            while (parent[v] != null){
                path = parent[v] + "->" + path;
                v = getPos(parent[v]);
            }
            System.out.println(path);
        }
    }

    public diGraphAdList(int size) {
        this.size = size;
        adLists = new diAdList[size];
        for (int i = 0; i < size; i++) {
            adLists[i] = new diAdList();
        }
    }

    public void addNode(String value, int weight, int pos){
        adLists[pos].add(value, weight);
    }

    public void showGraphAdList(){
        for (int i = 0; i < size; i++) {
            adLists[i].showList();
            System.out.println();
        }
    }
}